package medium;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/3/19 11:00
 */
public class No75_颜色分类 {
    public static void main(String[] args) {
        Solution75 solution75 = new Solution75();
        int[] nums = new int[]{0, 1, 0, 0, 1, 2, 1, 1, 2, 0, 1};
        //int[] nums = new int[]{2,0,2,1,1,0};
        solution75.sortColors(nums);
        System.out.println(nums);
    }
}

class Solution75 {
    public void sortColors(int[] nums) {
        // 进阶:一次遍历
        
        //red:0最右边界
        int red = 0;
        //green:2:最左边界
        int green = nums.length - 1;
        
        //遍历
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                //遇到0,则交换,然后red++
                swap(nums, red, i);
                red++;
            } else if (nums[i] == 2) {
                //遇到2,扔尾,注意,如果交换完,值是2,则继续--绿指针继续操作
                while (i<green && nums[i] == 2) {
                    swap(nums, i, green);
                    green--;
                }
                //交换完值是0,则必须交换
                if (nums[i] == 0) {
                    swap(nums, i, red);
                    red++;
                }
            }
        }
    }

    //交换
    public void swap(int[] nums, int a, int b) {
        //将a,b位置值交换
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}



    //public void sortColors(int[] nums) {
    //    // 二次遍历
    //    // 第一次遍历,0在前,第二次遍历1在前
    //    // 0000xxxx    00001112222...
    //    
    //    //red:待存放0的位置
    //    int red = 0;
    //    //green:去找0
    //    int green = 0;
    //    while (green < nums.length) {
    //        //开始找0,找到则存,再下一个
    //        if (nums[green] == 0) {
    //            //交换
    //            int tmp = nums[red];
    //            nums[red] = nums[green];
    //            nums[green] = tmp;
    //            //下一个
    //            red++;
    //        }
    //        //green找0
    //        green++;
    //    }
    //    
    //    //第一次遍历完,0肯定在最前面
    //    //注意,green重置
    //    green = red;
    //    while (green < nums.length) {
    //        //开始找1,找到则存,再下一个
    //        if (nums[green] == 1) {
    //            //交换
    //            int tmp = nums[red];
    //            nums[red] = nums[green];
    //            nums[green] = tmp;
    //            //下一个
    //            red++;
    //        }
    //        //green找1
    //        green++;
    //    }
    //}



    //public void sortColors(int[] nums) {
    //    //排序
    //    //快速排序
    //    sortColors(nums, 0, nums.length - 1);
    //}
    //
    //public void sortColors(int[] nums, int left, int right) {
    //    if (left > right) {
    //        return;
    //    }
    //    int a = left;
    //    int b = right;
    //    //基准元素
    //    int base = nums[left];
    //    
    //    //开始操作ab,注意可能多个交换情况
    //    while (a < b) {
    //        //从右到左找小,从左到右找大
    //        while (a < b && nums[b] >= base) {
    //            //一直找小
    //            b--;
    //        }
    //        while (a < b && nums[a] <= base) {
    //            //一直找大
    //            a++;
    //        }
    //        
    //        //a>b??????????? 注意不会!!
    //        if (a < b) {
    //            int tmp = nums[a];
    //            nums[a] = nums[b];
    //            nums[b] = tmp;
    //        }
    //    }
    //    
    //    //a=b,交换基准
    //    nums[left] = nums[a];
    //    nums[a] = base;
    //
    //    sortColors(nums, left, a - 1);
    //    sortColors(nums, a + 1, right);
    //}





